//! Radix Tree(aka Patricia Trie)
//!
//! #### 算法说明
//! - 压缩前缀树，检索效率高，存储空间占用小。
//!
//! #### 应用场景
//! - 增删改查。
//!
//! #### 实现属性
//! - <font color=Green>√</font> 多线程安全
//! - <font color=Red>×</font> 无 unsafe 代码

include!("macros.rs");
pub mod error;
pub mod traits;

use std::marker::PhantomData;
use std::rc::{Rc, Weak};

use error::*;
use traits::*;

#[derive(Default)]
pub struct Radix<T, K, V>
where
    T: Item,
    K: Key<T>,
{
    root: Vec<Rc<Node<T, V>>>, //顶层节点集合
    node_cnt: usize,           //节点总数
    _k: PhantomData<K>,
}

pub struct Node<T, V>
where
    T: Item,
{
    kfield: Box<[T]>,
    value: Option<Rc<V>>,

    upper: Weak<Node<T, V>>,
    children: Vec<Rc<Node<T, V>>>,
}

struct OkInfo<T: Item, V> {
    idx_in_children: usize, //节点在其父节点children中所处的位置索引
    node: Rc<Node<T, V>>,
}

///- @idx_in_children: 新值可以被插入的位置索引
///- @idx_in_key: 出现不匹配节点时, key与之进行比较的起始元素索引
///> 如:
///>     key = "abcd",
///>     在第一层成功匹配到kfield为"ab"的节点,
///>     假设第二层只存在一个节点, 其kfield为"ce", 则在第二层会匹配失败,
///>     此时, idx_in_key应置为2, 而不是3
pub struct ErrInfo<T: Item, V> {
    pub idx_in_children: usize,
    pub idx_in_key: usize,
    pub upper: Weak<Node<T, V>>,
}

impl<T, K, V> Radix<T, K, V>
where
    T: Item,
    K: Key<T>,
{
    #[inline(always)]
    pub fn new() -> Radix<T, K, V> {
        Radix {
            root: vec![],
            node_cnt: 0,
            _k: PhantomData,
        }
    }

    //返回两个切片的共同前缀, 无则返回None
    #[inline(always)]
    fn common_prefix<'a>(a: &'a [T], b: &[T]) -> Option<&'a [T]> {
        if let Some(i) = a.iter().zip(b.iter()).position(|(i, j)| i != j) {
            return Some(get!(a, ..i));
        }
        None
    }

    /// 置新值
    #[inline(always)]
    pub fn put(&mut self, key: K, value: V) -> Result<(), XErr> {
        self.put_x(key.into_boxed_slice(), value)
    }

    /// 置新值
    pub fn put_x(&mut self, key: Box<[T]>, value: V) -> Result<(), XErr> {
        let mut raw;
        match self.locate(&key[..]) {
            Err(ZErr::NoValue(node)) => {
                chg!(@node, value, Some(Rc::new(value)), raw);
            }
            Err(ZErr::NotExists(info)) => {
                // 若发现有共同前缀但不完全匹配的兄弟节点,
                // locate函数会将idx_in_children置为该兄弟节点的索引
                let u;
                let children = if let Some(upper) = Weak::upgrade(&info.upper) {
                    u = upper;
                    &u.children
                } else {
                    &self.root
                };

                if info.idx_in_children < children.len() {
                    let mut kfield;

                    /* 可能存在共同前缀 */
                    if let Some(pfx) =
                        Self::common_prefix(&key, &get!(children, info.idx_in_children).kfield)
                    {
                        /* 有共同前缀, 需要路径分裂 */
                        // 新分支节点
                        kfield = pfx.to_owned().into_boxed_slice();
                        let mut newbranch = Rc::new(Node {
                            kfield,
                            value: None,
                            upper: Weak::clone(&info.upper),
                            children: Vec::with_capacity(0),
                        });

                        // 原节点(与新建节点具有共同前缀)降到下一级
                        let mut curnode = Rc::clone(get!(children, info.idx_in_children));
                        kfield = get!(curnode.kfield, pfx.len()..)
                            .to_owned()
                            .into_boxed_slice();
                        chg!(curnode, kfield, kfield, raw);
                        chg!(curnode, upper, Rc::downgrade(&newbranch), raw);

                        // 新建的节点
                        kfield = get!(key, info.idx_in_key + pfx.len()..)
                            .to_owned()
                            .into_boxed_slice();
                        let newnode = Rc::new(Node {
                            kfield,
                            value: Some(Rc::new(value)),
                            upper: Rc::downgrade(&newbranch),
                            children: Vec::with_capacity(0),
                        });

                        // 关联: 分支与叶
                        let chdren = if get!(curnode.kfield, 0) < get!(newnode.kfield, 0) {
                            vec![curnode, newnode]
                        } else {
                            vec![newnode, curnode]
                        };
                        chg!(newbranch, children, chdren, raw);

                        // 用新的分支节点替换原节点的位置
                        unsafe {
                            std::ptr::replace(
                                get!(^children, info.idx_in_children) as *const Rc<Node<T, V>>
                                    as *mut Rc<Node<T, V>>,
                                newbranch,
                            );
                        }
                    } else {
                        /* 无共同前缀, 直接插入 */
                        put_default!(self, info, key, value, raw);
                    }
                } else {
                    /* 插入点在末尾, 不存在共同前缀 */
                    put_default!(self, info, key, value, raw);
                }
            }
            Err(e) => return Err(e.into()),
            Ok(_) => return Err(XErr::AlreadyExists),
        };

        self.node_cnt += 1;
        Ok(())
    }

    /// 删除已有节点
    #[inline(always)]
    pub fn del(&mut self, key: K) -> Result<(), XErr> {
        self.del_x(&key.into_boxed_slice()[..])
    }

    /// 删除已有节点
    pub fn del_x(&mut self, key: &[T]) -> Result<(), XErr> {
        let info = self.locate(key).map_err(XErr::from)?;
        let mut raw;

        if info.node.children.is_empty() {
            del!(self, info, raw);
        } else if 1 == info.node.children.len() {
            /* 非叶节点, 只有一个子节点 */
            let mut newkey = info.node.kfield.to_vec();
            let mut replacer = Rc::clone(get!(info.node.children, 0));
            newkey.extend_from_slice(&replacer.kfield);
            chg!(replacer, kfield, newkey.into_boxed_slice(), raw);

            if let Some(upper) = Weak::upgrade(&info.node.upper) {
                raw = Rc::into_raw(upper) as *mut Node<T, V>;
                unsafe {
                    *get_mut!(^(*raw).children, info.idx_in_children) = replacer;
                    Rc::from_raw(raw);
                }
            } else {
                *get_mut!(self.root, info.idx_in_children) = replacer;
            }
        } else {
            /* 非叶节点, 有多个子节点 */
            chg!(@info.node, value, None, raw);
        }

        self.node_cnt -= 1;
        Ok(())
    }

    /// 更新已有K的值
    #[inline(always)]
    pub fn update(&self, key: K, value: V) -> Result<(), XErr> {
        self.update_x(&key.into_boxed_slice()[..], value)
    }

    /// 更新已有K的值
    #[inline(always)]
    pub fn update_x(&self, key: &[T], value: V) -> Result<(), XErr> {
        let info = self.locate(key).map_err(XErr::from)?;
        chg!(@info.node, value, Some(Rc::new(value)));
        Ok(())
    }

    /// 据K获V
    #[inline(always)]
    pub fn get(&self, key: K) -> Result<Rc<V>, XErr> {
        self.get_x(&key.into_boxed_slice()[..])
    }

    /// 据K获V
    #[inline(always)]
    pub fn get_x(&self, key_slice: &[T]) -> Result<Rc<V>, XErr> {
        self.locate(key_slice)
            .map(|info| Rc::clone(info.node.value.as_ref().unwrap()))
            .map_err(XErr::from)
    }

    /// 节点总数
    #[inline(always)]
    pub fn node_cnt(&self) -> usize {
        self.node_cnt
    }

    /// 获取K所在节点
    fn locate(&self, key: &[T]) -> Result<OkInfo<T, V>, ZErr<T, V>> {
        match self
            .root
            .binary_search_by(|n| n.kfield[..].cmp(get!(key, ..n.kfield.len())))
        {
            Ok(idx) => {
                if key.len() == get!(self.root, idx).kfield.len() {
                    if get!(self.root, idx).value.is_some() {
                        Ok(OkInfo {
                            idx_in_children: idx,
                            node: Rc::clone(get!(self.root, idx)),
                        })
                    } else {
                        Err(ZErr::NoValue(Rc::clone(get!(self.root, idx))))
                    }
                } else {
                    /* 二分查找返回Ok, 则key.len() >= kfield.len()一定成立,
                     * 故无需考虑key比kfield短的情况 */
                    Self::locate_inner(
                        Rc::clone(get!(self.root, idx)),
                        key,
                        get!(self.root, idx).kfield.len(),
                    )
                }
            }
            Err(idx) => {
                if 0 < idx && get!(key, 0) == get!(get!(^self.root, idx - 1).kfield, 0) {
                    Err(ZErr::NotExists(ErrInfo {
                        idx_in_children: idx - 1,
                        idx_in_key: 0,
                        upper: Weak::new(),
                    }))
                } else {
                    Err(ZErr::NotExists(ErrInfo {
                        idx_in_children: idx,
                        idx_in_key: 0,
                        upper: Weak::new(),
                    }))
                }
            }
        }
    }

    // **should be a tail-recursion**
    fn locate_inner(
        entry: Rc<Node<T, V>>,
        key: &[T],
        startidx: usize,
    ) -> Result<OkInfo<T, V>, ZErr<T, V>> {
        let idx;
        match entry
            .children
            .binary_search_by(|n| n.kfield[..].cmp(get!(key, startidx..startidx + n.kfield.len())))
        {
            Ok(i) => {
                if get!(key, startidx..).len() == get!(entry.children, i).kfield.len() {
                    if get!(entry.children, i).value.is_some() {
                        return Ok(OkInfo {
                            idx_in_children: i,
                            node: Rc::clone(get!(entry.children, i)),
                        });
                    } else {
                        return Err(ZErr::NoValue(Rc::clone(get!(entry.children, i))));
                    }
                } else {
                    // **进入下一轮递归**
                    // 二分查找返回Ok, 则key.len() >= kfield.len()一定成立,
                    // 故无需考虑key比kfield短的情况
                    idx = i;
                }
            }
            Err(i) => {
                if 0 < i && get!(key, 0) == get!(get!(^entry.children, i - 1).kfield, 0) {
                    return Err(ZErr::NotExists(ErrInfo {
                        idx_in_children: i - 1,
                        idx_in_key: startidx,
                        upper: Rc::downgrade(&entry),
                    }));
                } else {
                    return Err(ZErr::NotExists(ErrInfo {
                        idx_in_children: i,
                        idx_in_key: startidx,
                        upper: Rc::downgrade(&entry),
                    }));
                }
            }
        };

        Self::locate_inner(
            Rc::clone(get!(entry.children, idx)),
            key,
            startidx + get!(entry.children, idx).kfield.len(),
        )
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use rand::Rng;

    fn gen_sample(total: u32) -> Vec<Box<[i32]>> {
        let mut rng = rand::thread_rng();
        let mut sample = vec![];
        let mut v;

        for _ in 0..total {
            v = vec![];
            (0..100).for_each(|_| v.push(rng.gen::<i32>()));
            sample.push(v.into_boxed_slice());
        }

        sample.sort();
        sample.dedup();
        sample
    }

    fn function_test(sample: &[Box<[i32]>]) {
        let mut radix = Radix::new();

        sample
            .iter()
            .cloned()
            .for_each(|i| radix.put(i, 0).unwrap());
        assert_eq!(sample.len(), radix.node_cnt);

        sample.iter().cloned().for_each(|i| {
            assert_eq!(0, *radix.get_x(&i[..]).unwrap());
            radix.update_x(&i[..], 1).unwrap();
            assert_eq!(1, *radix.get_x(&i[..]).unwrap());
            radix.del_x(&i[..]).unwrap();
            assert!(radix.get_x(&i[..]).is_err());
        });

        assert_eq!(0, radix.node_cnt);
    }

    #[test]
    fn entry() {
        let sample;
        if cfg!(debug_assertions) {
            sample = gen_sample(100);
        } else {
            sample = gen_sample(10000);
        };

        function_test(&sample);
    }
}
